LeetCode 334、递增的三元组

一、题目描述

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,4,5] 输出：true 解释：任何 i < j < k 的三元组都满足题意

示例 2：

输入：nums = [5,4,3,2,1] 输出：false 解释：不存在满足题意的三元组

示例 3：

输入：nums = [2,1,5,0,4,6] 输出：true 解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6

提示：

• 1 <= nums.length <= 5 * 10^5
• -2^31 <= nums[i] <= 2^31 - 1

**进阶：**你能实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案吗？

二、题目解析

三、参考代码

1、Java 代码

// 超时代码
class Solution {
    public boolean increasingTriplet(int[] nums) {

        // 设置数组 dp，用来存储 nums 中以每个元素结尾的最长递增序列的程度
        // dp[0] 表示以 nums[0] 结尾的最长递增序列的长度
        // dp[1] 表示以 nums[1] 结尾的最长递增序列的长度
        // dp[i] 表示以 nums[i] 结尾的最长递增序列的长度
        int[] dp = new int[nums.length];

        // 首先将数组 dp 里面的值都初始化为 1
        // 1 表示以当前元素结尾的最长递增序列的长度为 1
        // 即最长递增序列就是当前元素本身
        Arrays.fill(dp, 1);

        // 设置一个变量用来存储最长递增序列的结果
        int maxLength = 1;

        // 从 1 开始，直到 dp.length ，往 dp 里面填充结果
        for(int i = 1 ; i < dp.length ; i++){

            // 对于 dp[i] 来说，在 nums 中从 0 到 i - 1 都是在 i 的前面的
            // 比如 nums 为 [1,5,2,5,3,7,2]
            // 此时 i 为 3，那么 1,5,2 这些数字都在索引位置为 3 的前面
            // 从 0 遍历到 i - 1，就可以从这些数字中选出小于 i 的数字
            for(int j = 0; j < i ;j++){
               
                // 索引      0  1  2  3  4  5  6
                // nums 为 [ 1, 5, 2, 5, 3, 7, 2 ]
                // 此时 i 为 3，那么 1,5,2 这些数字都在索引位置为 3 的前面
                // 1、从这些数字中选出小于 nums[i] 的数字
                // 2、小于 nums[i] 的那些数字是 1 , 2 ，在之前都已经计算过以 1 或者 2 结尾的最长递增序列的长度
                // 并且这个结果存放在 dp[j] 中
                // 如果数字为 1，那么此时 j 为 0，dp[0] 存放了以 1  结尾的最长递增序列的长度
                // 如果数字为 2，那么此时 j 为 2，dp[2] 存放了以 2  结尾的最长递增序列的长度
                // 3、如果发现此时 dp[i] 小于了 dp[j] + 1
                // 4、说明此时 dp[i] 中的值就不是以 nums[i] 结尾的最长递增序列的长度
                // 需要更新 dp[i]
                if(nums[i] > nums[j] && dp[i] < dp[j] + 1){
                    // 4、更新 dp[i]
                    dp[i] = dp[j] + 1;
                }
            }

            // 在更新 dp[i] 的过程中，发现了一个更长的子序列
            if(maxLength < dp[i]){
                // 那么把更长的子序列的长度赋值给 maxLength
                maxLength = dp[i];
            }

            if( maxLength >= 3) return true;
        }

        // 最后返回 maxLength 就行
        return false;

    }
}

Python

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:

        # 三元组里面最小的数
        first = float('inf')

        # 三元组里面中间的那个数
        second = float('inf')

        # 开始寻找第三个数
        for third in nums:
            # 1、第三个数 大于 了之前确定好的 第二个数
            # 说明找到了满足条件的三元组
            if third > second: return True

            # 2、第三个数 小于 了之前确定好的 第一个数
            # 为了能让后续 第二个数 的可选范围更大
            # 第一个数总是应该越小越好
            # 这样 第二个数 的可选范围更大
            # 导致 第三个数 的可选范围也更大
            # 更能找到满足条件的三元组
            elif third <= first: first = third

            # 3、第三个数的值介于 first 和 second 中间
            # 更新 second 的值
            # 第二个数小一些
            # 导致 第三个数 的可选范围也更大
            # 更能找到满足条件的三元组
            else: second = third
        
        # 返回结果
        return False